Number of dice rolls with target sum

Time: O(DxFxT); Space: O(T); medium

You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1:

Input: d = 1, f = 6, target = 3

Output: 1

Explanation:

  • You throw one die with 6 faces.

  • There is only one way to get a sum of 3.

Example 2:

Input: d = 2, f = 6, target = 7

Output: 6

Explanation:

  • You throw two dice, each with 6 faces.

  • There are 6 ways to get a sum of 7:

    • 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: d = 2, f = 5, target = 10

Output: 1

Explanation:

  • You throw two dice, each with 5 faces.

  • There is only one way to get a sum of 10: 5+5.

Example 4:

Input: d = 1, f = 2, target = 3

Output: 0

Explanation:

  • You throw one die with 2 faces.

  • There is no way to get a sum of 3.

Example 5:

Input: d = 30, f = 30, target = 500

Output: 222616187

Explanation:

  • The answer must be returned modulo 10^9 + 7.

Constraints:

  • 1 <= d, f <= 30

  • 1 <= target <= 1000

Hints:

  1. Use dynamic programming. The states are how many dice are remaining, and what sum total you have rolled so far.

1. Dynamic programming [O(DxFxT), O(T)]

[1]:

class Solution1(object):
    """
    Time: O(D*F*T)
    Space: O(T)
    """
    def numRollsToTarget(self, d, f, target):
        """
        :type d: int
        :type f: int
        :type target: int
        :rtype: int
        """
        MOD = 10**9+7
        dp = [[0 for _ in range(target+1)] for _ in range(2)]
        dp[0][0] = 1

        for i in range(1, d+1):
            dp[i%2] = [0 for _ in range(target+1)]
            for k in range(1, f+1):
                for j in range(k, target+1):
                    dp[i%2][j] = (dp[i%2][j] + dp[(i-1)%2][j-k]) % MOD

        return dp[d%2][target] % MOD

[2]:

s = Solution1()

d = 1
f = 6
target = 3
assert s.numRollsToTarget(d, f, target) == 1

d = 2
f = 6
target = 7
assert s.numRollsToTarget(d, f, target) == 6

d = 2
f = 5
target = 10
assert s.numRollsToTarget(d, f, target) == 1

d = 1
f = 2
target = 3
assert s.numRollsToTarget(d, f, target) == 0

d = 30
f = 30
target = 500
assert s.numRollsToTarget(d, f, target) == 222616187